package code.homework;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author cc
 * @create 2023-02-26  20:59
 */
public class FindCircleNum {

    /**
     * INIT(x)
     *     x.parent := x
     *     x.size := 1
     * FIND(x)
     *     if x.parent != x:
     *         x.parent := FIND(x.parent)
     *     return x.parent
     * UNION(x, y)
     *     x := FIND(x)
     *     y := FIND(y)
     *     if x = y:
     *         return  # loop detected!
     *     if x.size < y.size:
     *         (x, y) := (y, x)
     *     y.parent := x
     *     x.size := x.size + y.size
     *
     */
    public static int findCircleNum(int[][] isConnected) {
        List<Node> nodes = new ArrayList<>();
        for (int i = 0 ;i < isConnected.length ; i++){
            nodes.add(init(i));
        }

        for (int i = 0 ;i< isConnected.length; i++) {
            for (int j = 0; j< isConnected.length; j++){
                if(isConnected[i][j] == 1){
                    union(nodes.get(i),nodes.get(j));
                }
            }
        }

        Set<Integer> set = new HashSet<Integer>();
        nodes.stream().forEach(o->set.add(o.parent.value));
        return set.size();
    }

    static Node find(Node node){
        if(node.parent.value != node.value){
            node.parent = find(node.parent);
        }
        return node.parent;
    }

    static void union(Node node1,Node node2){
        Node parent1 = find(node1);
        Node parent2 = find(node2);
        if(parent1.value == parent2.value){
            return;
        }
        if(parent1.value < parent2.value){
            parent2.parent = parent1;
        }else {
            parent1.parent = parent2;
        }
    }

    static Node init(int x){
        Node node = new Node();
        node.value = x;
        return node;
    }

    static class Node {
        int value;
        Node parent = this;
        int size = 1;
    }

    public static void main(String[] args) {
        int[][] isConnected = new int[][]{{1,1,0,0,0,0,0,1,0,0,0,0,0,0,0},{1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0,1,1,0,0,0,0},{0,0,0,1,0,1,0,0,0,0,1,0,0,0,0},{0,0,0,1,0,0,1,0,1,0,0,0,0,1,0},{1,0,0,0,0,0,0,1,1,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,0,0,0,0,1,0},{0,0,0,0,1,0,0,0,0,1,0,1,0,0,1},{0,0,0,0,1,1,0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,1,0,1,0,0,0,0,1,0},{0,0,0,0,0,0,0,0,0,1,0,0,0,0,1}};
        findCircleNum(isConnected);
    }

}
